package demo.practice.leetcode_eveyday;

import demo.practice.TreeNode;

import java.util.List;
import java.util.Stack;

public class P872 {

    List<Integer> list = new Stack<>();

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        //从左到右的叶节点   必须中序遍历
        foreachBefor(root1);
        int len = list.size();
        foreachBefor(root2);
        if (list.size() != 2 * len)
            return false;
        len = list.size();

        for (int i = 0; i < len / 2; i++) {
            if (!list.get(i).equals(list.get(i + len / 2)))
                return false;
        }
        return true;
    }


    public void foreachBefor(TreeNode root1) {
        if (root1 == null) {
            return;
        }
        if (root1.left == null && root1.right == null) {
            list.add(root1.val);
            return;
        }
        if (root1.left != null)
            foreachBefor(root1.left);
        //当前节点跳过
        if (root1.right != null)
            foreachBefor(root1.right);
    }


}
